package 分类.回溯;

import java.util.*;

public class 子集 {
    static ArrayList<ArrayList<Integer>> res=new ArrayList<>();
    static ArrayList<Integer> track=new ArrayList<>();
    //无重复元素
    public static ArrayList<ArrayList<Integer>> subsets(int[] nums) {
        back(nums,0);
        return res;
    }

    static void back(int[] nums,int start){
        res.add(new ArrayList<>(track));
        for (int i=start;i<nums.length;i++){
            track.add(nums[i]);
            back(nums,i+1);
            track.remove(track.size()-1);
        }
    }
    //有重复元素


    public static ArrayList<ArrayList<Integer>> subsetsWithDup(int[] nums) {
        // 先排序，让相同的元素靠在一起
        Arrays.sort(nums);
        backtrack(nums, 0);
        return res;
    }

    static void backtrack(int[] nums, int start) {
        // 前序位置，每个节点的值都是一个子集
        res.add(new ArrayList<>(track));

        for (int i = start; i < nums.length; i++) {
            // 剪枝逻辑，值相同的相邻树枝，只遍历第一条
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            track.add(nums[i]);
            backtrack(nums, i + 1);
            track.remove(track.size()-1);
        }
    }



    static int zishcountDistinctuzu(int[] nums,int k,int p){
       int ans=0;
       Set<String> set=new HashSet<>();
        for (int i=0;i<nums.length;i++){
            StringBuilder sb=new StringBuilder();
            int cnt=0;
            for (int j=i;j>=0;j--){

                sb.append(nums[j]+" ");
                if(nums[j]%p==0) cnt++;
                if(cnt<=k&&!set.contains(sb.toString())){
                    set.add(sb.toString());
                    ans++;
                }
            }

        }
        return ans;
    }
    /*
    class Solution {
   public int countDistinct(int[] nums, int k, int p) {
		int ans=0;
		Set<String> set=new HashSet<>();//去重使用
		for (int i = 0; i < nums.length; i++) {
			int cnt=0;//保存当前子串中可被 p 整除的元素的数量
			StringBuilder builder=new StringBuilder();
			for (int j = i; j >= 0; j--) {
				builder.append(nums[j]+" ");//必须要空格，不然不能去重
				if(nums[j]%p==0) cnt++;
				if(cnt<=k&&!set.contains(builder.toString())) {
					set.add(builder.toString());//使用HashSet进行子数组进行去重
					ans++;
				}
			}
		}

		return ans;
    }
}


     */

    public static void main(String[] args) {
        int[] nums={1,2,3};
        //List<List<Integer>> res=zishuzu(nums);


    }
}
